package com.example.javamaday.codetop;

import java.util.Arrays;

public class CodeTop0912 {

    public static void main(String[] args) {
        int[] result = new CodeTop0912().sortArray(new int[]{5, 2, 3, 1});
        System.out.println(Arrays.deepToString(new int[][]{result}));
    }

    // 快速排序
    public int[] sortArray(int[] nums) {
        if (nums.length <= 1) {
            return nums;
        }
        sortArray(nums, 0, nums.length - 1);
        return nums;
    }

    public void sortArray(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int partition = partition(nums, lo, hi);
        sortArray(nums, lo, partition - 1);
        sortArray(nums, partition + 1, hi);
    }

    private int partition(int[] nums, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        while (true) {
            while (nums[++i] < nums[lo]) {
                if (i == hi) {
                    break;
                }
            }
            while (nums[--j] > nums[lo]) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exchange(nums, i, j);
        }
        exchange(nums, lo, j);
        return j;
    }


    private void exchange(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
